class Node:
    def __init__(self, x, next=None, random=None):
        self.val = int(x)
        self.next = next
        self.random = random


class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return None
        new_head = Node(head.val)
        node = head
        already_node = {head: new_head}
        new_node = new_head
        while node:
            if node.random:
                if node.random in already_node:
                    new_node.random = already_node[node.random]
                else:
                    create_new = Node(node.random.val)
                    already_node[node.random] = create_new
                    new_node.random = create_new
            if node.next:
                if node.next in already_node:
                    new_node.next = already_node[node.next]
                else:
                    create_new = Node(node.next.val)
                    already_node[node.next] = create_new
                    new_node.next = create_new
            node = node.next
            new_node = new_node.next
        return new_head



